Convex body collision detection using the signed distance function

P. López-Adeva Fernández-Layos, L.F. S. Merchante

Computer-Aided Design Vol. 170, pp. 103685-1 - 103685-16

Summary:

We present a new algorithm to compute the minimum distance and penetration depth between two convex bodies represented by their Signed Distance Function (SDF). First, we formulate the problem as an optimization problem suitable for arbitrary non-convex bodies, and then we propose the ellipsoid algorithm to solve the problem when the two bodies are convex. Finally, we benchmark the algorithm and compare the results in collision detection against the popular Gilbert–Johnson–Keerthi (GJK) and Minkowski Portal Refinement (MPR) algorithms, which represent bodies using the support function. Results show that our algorithm has similar performance to both, providing penetration depth like MPR and, with better robustness, minimum distance like GJK. Our algorithm provides accurate and fast collision detection between implicitly modeled convex rigid bodies and is able to substitute existing algorithms in previous applications whenever the support function is replaced with the SDF.

Spanish layman's summary:

El artículo describe un algoritmo para determinar la distancia mínima y la profundidad de penetración entre cuerpos convexos usando la Signed Distance Function (SDF), superando al algoritmo de Gilbert–Johnson–Keerthi (GJK) y al Minkowski Portal Refinement (MPR) en la detección de colisiones.

English layman's summary:

The article presents a new algorithm for determining the minimum distance and penetration depth between convex bodies using their Signed Distance Function (SDF), outperforming the Gilbert–Johnson–Keerthi (GJK) and Minkowski Portal Refinement (MPR) algorithms in computing minimum distances.

Keywords: Signed distance function; Collision detection; Ellipsoid method

JCR Impact Factor and WoS quartile: 3,000 - Q2 (2023)

DOI reference: https://doi.org/10.1016/j.cad.2024.103685

Published on paper: May 2024.

Published on-line: February 2024.

Citation:
P. López-Adeva Fernández-Layos, L.F. S. Merchante, Convex body collision detection using the signed distance function. Computer-Aided Design. Vol. 170, pp. 103685-1 - 103685-16, May 2024. [Online: February 2024]